package ST;


/**
 * https://oi-wiki.org/ds/sparse-table/
 * 解决重复性贡献的问题：
 * 例如：给定n个数，有m个询问，对于每一个询问[l, r] 区间的最大值。
 */

class Solution {
    int n;  // 数组的长度
    int[] arr; // 输入的数组

    int N = 1000006;
    int[] mn = new int[N];
    int[][] dp = new int[N][25];
    void rmq_init(){
        for (int i = 0; i <= n; i++)
            dp[i][0] = arr[i];
        for(int j = 1; (1 << j) <= n; j++)
            for (int i = 0; i + (1 << j) <= n ; i++)
                dp[i][j] = Math.min(dp[i][j-1], dp[i + (1 << j -1)][j-1]);
        
        for(int len = 1; len <= n; ++len){
            int k = 0;
            while ((1 << (k + 1) <= len)){
                k++;
            }
            mn[len] = k;
        }
    }
    int rmq(int l, int r){
        int k = mn[r - l + 1];
        return Math.min(dp[l][k], dp[r - (1 << k) + 1][k]);
    }
}